Theory of Computation
Q141.
Let < M > denote an encoding of an automaton M. Suppose that \Sigma =\{0,1\}. Which of the following languages is/are NOT recursive?Q142.
If L and P are two recursively enumerable languages then they are not closed underQ143.
Given the following statementsS1 : Every context-sensitive language L is recursiveS2 : There exists a recursive language that is not context-sensitiveWhich statements are true?Q145.
Let L be a language and \bar{L} be its complement. Which of the following is NOT a viable possibility?Q148.
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that \bar{Y} reduces to W, and Z reduces to \bar{X} (reduction means the standard many-one-reduction). Which one of the following statements is TRUE?Q149.
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?Q150.
Let L1 be regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?